use std::rc::Rc;

#[derive(Clone, Debug, Eq, PartialEq)]
pub enum BinarySearchTree<T> {
    Leaf,
    Node(Rc<BinarySearchTree<T>>, T, Rc<BinarySearchTree<T>>),
}

use self::BinarySearchTree::{Leaf, Node};

impl<T: Ord + Clone> BinarySearchTree<T> {
    pub fn empty() -> BinarySearchTree<T> {
        Leaf
    }

    pub fn count(&self) -> i32 {
        match *self {
            Leaf => 0,
            Node(ref left, _, ref right) => 1 + left.count() + right.count(),
        }
    }

    pub fn elements(&self) -> Vec<T> {
        match *self {
            Leaf => vec![],
            Node(ref left, ref x, ref right) => {
                let mut tmp = left.elements();
                let mut tmp1 = vec![x.clone()];
                let mut tmp2 = right.elements();
                tmp.append(&mut tmp1);
                tmp.append(&mut tmp2);
                tmp
            }
        }
    }
    pub fn is_empty(&self) -> bool {
        Leaf == *self
    }

    pub fn contains(&self, x: T) -> bool {
        match *self {
            Leaf => false,
            Node(_, ref v, _) if x == *v => true,
            Node(ref left, ref v, _) if x < *v => left.contains(x),
            Node(_, ref v, ref right) if x > *v => right.contains(x),
            _ => false,
        }
    }

    pub fn insert(&self, val: T) -> Self {
        match *self {
            Leaf => Node(Rc::new(Leaf), val, Rc::new(Leaf)),
            Node(ref left, ref x, ref right) => {
                if val < *x {
                    return Node(Rc::new(left.insert(val.clone())), x.clone(), right.clone());
                } else if val > *x {
                    return Node(left.clone(), x.clone(), Rc::new(right.insert(val.clone())));
                }
                self.clone()
            }
        }
    }
}

#[test]
fn binary_search_tree_test() {
    let tree: BinarySearchTree<i32> = BinarySearchTree::empty();
    let copied = tree.insert(5);
    assert_eq!(copied.elements(), vec![5]);
}
